home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 17 / CU Amiga Magazine's Super CD-ROM 17 (1997)(EMAP Images)(GB)[!][issue 1997-12].iso / CUCD / Programming / DiceSource / lib / stdlib / bsearch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-09-09  |  1.6 KB  |  69 lines

  1.  
  2. /*
  3.  *  BSEARCH.C
  4.  *
  5.  *    (c)Copyright 1992-1997 Obvious Implementations Corp.  Redistribution and
  6.  *    use is allowed under the terms of the DICE-LICENSE FILE,
  7.  *    DICE-LICENSE.TXT.
  8.  *
  9.  *  BSearch() - binary search of an array
  10.  *
  11.  *  note that aryEnd is the number of elements in the array and therefore
  12.  *  base[aryEnd * objSize] is an INVALID element and not included in the
  13.  *  search (e.g. just past the end of the array).
  14.  */
  15.  
  16. #include <stdlib.h>
  17. #include <string.h>
  18.  
  19. void *
  20. bsearch(key, base, aryEnd, objSize, compare)
  21. void *key;
  22. void *base;
  23. size_t aryEnd;
  24. size_t objSize;
  25. int (*compare)(const void *key, const void *elm);
  26. {
  27.     static short Power = -1;    /*  power of 2 optimization */
  28.     size_t aryBeg = 0;
  29.     long   r;
  30.     short power = Power;
  31.  
  32.     if (power < 0 || (1 << power) != objSize) {
  33.     for (power = 0; (r = (1 << power)) && (unsigned long)r < objSize; ++power)
  34.         ;
  35.     if (r != objSize)
  36.         power = -1;
  37.     Power = power;
  38.     }
  39.     if (power >= 0) {
  40.     while (aryBeg < aryEnd) {
  41.         size_t i = (aryBeg + aryEnd) >> 1;
  42.         void *obj = (void *)((char *)base + (i << power));
  43.  
  44.         r = compare(key, obj);
  45.         if (r < 0)            /*    we are over the object */
  46.         aryEnd = i;
  47.         else if (r > 0)        /*    we are under the object  */
  48.         aryBeg = i + 1;
  49.         else
  50.         return(obj);
  51.     }
  52.     } else {
  53.     while (aryBeg < aryEnd) {
  54.         size_t i = (aryBeg + aryEnd) >> 1;
  55.         void *obj = (void *)((char *)base + i * objSize);
  56.  
  57.         r = compare(key, obj);
  58.         if (r < 0)            /*    we are over the object */
  59.         aryEnd = i;
  60.         else if (r > 0)        /*    we are under the object  */
  61.         aryBeg = i + 1;
  62.         else
  63.         return(obj);
  64.     }
  65.     }
  66.     return(NULL);
  67. }
  68.  
  69.